package 矩阵最短路径;

import java.util.Scanner;


/*矩阵最短路径问题：
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
从矩阵左上角出发，每次只能选择向右或向下走，到达矩阵右下角点所经过点的权值总和最小为多少。*/
public class MinPath {
    public static int getMin(int[][] map, int n, int m) {//map 数组用来存放矩阵中的元素  n和m 表示行和列
        int[][] dp = new int[n][m];
        for(int i=0;i<n;i++){
            for(int j=0;j<=i;j++){
                dp[i][0]+=map[j][0]; //向下走
            }
        }
        for(int i=0;i<m;i++){
            for(int j=0;j<=i;j++){
                dp[0][i]+=map[0][j];  //向右走
            }
        }


        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                dp[i][j] = min(dp[i][j-1]+map[i][j],dp[i-1][j]+map[i][j]);   //将最短的路径的情况存入数组中
            }
        }
        return dp[n-1][m-1];
    }
    public static int min(int a,int b){//定义一个方法  进行比较 使得最小
        if(a>b){
            return b;
        }else{
            return a;
        }
    }
    public static void main(String[] args){
        MinPath mp=new MinPath();
        System.out.println("请输入矩阵的行和列：");
        Scanner input=new Scanner(System.in);
        //可以后来改为键盘输入也行  优化后的
        int n=input.nextInt();
        int m=input.nextInt();

        /*int[][] dp =new int[][]{{1,3,5,9},{8,1,3,4},{5,0,6,1},{8,8,4,0}};*/
        int[][] dp =new int[n][m];
        System.out.println("请输入矩阵：");
        for(int i=0 ; i<n ; i++){//利用双重for循环从键盘输入矩阵的数据
            for(int j=0 ; j<m; j++){
                dp[i][j] = input.nextInt();
            }
        }
        int value=MinPath.getMin(dp,n,m);
        System.out.println("这个矩阵的最短路径的权值为："+value);
    }
}

